/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/missing-ranges
   @Language: C++
   @Datetime: 19-05-18 15:25
   */

class Solution {
public:
	/*
	 * @param nums: a sorted integer array
	 * @param lower: An integer
	 * @param upper: An integer
	 * @return: a list of its missing ranges
	 */
	vector<string> findMissingRanges(vector<int> &A, int lower, int upper) {
		// write your code here
		vector<string> vs;
		int l=lower_bound(A.begin(),A.end(),lower)-A.begin();
		int r=lower_bound(A.begin(),A.end(),upper)-A.begin();
		if(l==A.size()) return {to_string(lower)+(lower==upper?"":"->"+to_string(upper))};
		if(A[0]>lower) vs.push_back(to_string(lower)+(A[0]<lower+2?"":"->"+to_string(A[0]-1)));
		for(int i=l+1; i<=r; ++i){
			const int small=A[i-1], big=(i==A.size()?upper+1:A[i]);
			if(small==big) continue;
			if(big==small+2) vs.push_back(to_string(small+1));
			if(big-2>small) vs.push_back(to_string(small+1)+"->"+to_string(big-1));
		}
		return vs;
	}
};
